n=1000;
p=763;
a=[697,313,310,761,-481,93,745,516,382,-73,871,-881,497,517,-743,-954,-547,123,-751,615,166,-793,689,-296,236,-469,-651,301,156,-991,-852,381,921,-817,129,421,-943,-841,558,-675,-341,747,-851,317,775,-657,243,-385,345,67,-905,156,950,41,291,399,-655,-936,98,985,875,-131,573,-397,633,686,-465,59,525,-321,23,-751,633,-326,340,-876,217,-715,693,29,233,-501,-551,409,-665,-965,199,-283,664,-887,447,541,40,394,-305,403,427,68,931,177,-299,701,-270,811,-1,-685,359,649,898,-537,399,91,935,865,-209,625,-64,-371,884,781,537,62,-63,997,-777,649,461,807,-612,376,241,-457,887,-334,-384,-141,863,177,-587,-925,941,559,276,-861,657,-413,-748,137,-47,51,201,-565,985,641,999,983,665,-262,-326,-241,571,83,925,-351,875,-355,311,487,111,-54,813,604,89,896,576,649,261,431,-443,843,-129,536,289,-49,905,-690,-611,941,501,-383,-33,490,-175,176,851,457,373,-333,-737,929,-501,489,313,-291,746,979,439,121,225,921,721,77,753,817,-522,449,689,463,145,601,826,-857,-231,113,184,393,276,431,-899,761,1,-545,-578,-281,881,897,-761,-345,-217,129,618,-94,957,860,661,49,153,341,689,703,-526,153,-455,-971,725,135,377,441,841,91,945,603,-967,81,151,291,516,449,627,11,441,126,209,-418,-121,471,841,-666,953,-681,591,-561,403,-937,936,209,325,-657,1,718,-456,164,187,-61,-441,-711,-211,965,605,486,741,73,961,171,-243,633,941,-301,197,913,727,216,769,-81,-121,-169,-229,61,-126,689,930,9,81,706,636,-259,-944,-781,-313,76,-381,282,565,541,824,943,270,965,821,-225,231,295,393,792,954,-313,-499,681,326,-737,321,233,521,593,-589,-386,925,-908,367,39,692,-62,-325,-681,-105,701,281,795,945,207,-91,841,221,-957,593,-276,941,-189,711,871,-649,313,341,241,357,648,93,826,441,593,-712,914,-585,-713,-545,951,147,655,20,122,813,161,-105,51,-447,746,105,-681,229,886,725,393,365,21,105,81,-376,762,806,153,16,-261,245,337,191,178,273,-121,862,37,-145,671,737,865,-71,245,-261,-884,-881,-41,187,103,890,172,329,217,-420,694,67,-361,791,991,598,541,911,-41,718,13,-901,-297,824,-249,-438,297,-513,106,49,-843,518,143,289,567,369,961,606,-615,552,-517,-178,-265,-88,259,-936,-336,-163,156,836,161,33,-577,901,391,904,277,321,125,102,664,147,-553,427,305,-557,595,145,481,265,496,-649,140,293,51,-786,849,81,66,-862,753,131,-319,33,197,-781,-42,344,210,-629,101,-361,-297,19,261,111,-361,718,231,794,761,353,373,-69,704,-89,-506,927,921,-753,545,-993,197,-993,42,829,755,-689,337,-671,657,551,761,363,847,255,-281,453,873,-905,-242,777,-954,321,-1,152,859,953,339,-460,870,-230,85,894,-701,351,21,941,945,463,441,611,393,345,47,456,799,-39,625,-413,218,805,321,811,697,459,411,401,-217,401,567,961,-217,171,-135,955,-464,803,529,985,13,-901,273,-591,481,496,470,-861,390,353,978,1,1,-29,-507,676,69,233,-53,901,421,289,817,886,-216,-207,-853,-983,399,439,-921,-785,-904,855,521,393,251,575,-137,953,121,-677,539,320,161,765,696,665,159,97,-807,-189,717,-993,713,11,-545,537,-642,825,-393,345,-333,395,69,674,-641,-290,653,-965,-701,441,9,550,199,749,-72,225,401,171,872,648,951,-761,940,961,-234,301,-900,-939,601,56,603,-527,951,-561,593,200,-381,585,264,921,-673,87,393,481,533,825,-569,741,-345,621,633,362,-401,81,-685,-363,624,575,802,-52,649,906,172,-391,437,474,860,-261,377,-793,425,493,-653,370,545,921,169,490,246,446,85,131,7,-645,961,13,-446,-41,525,463,401,748,-193,501,859,11,-903,421,-489,891,-533,989,102,801,719,161,-335,536,241,-770,-280,-681,483,-151,413,499,570,417,995,393,393,951,921,596,694,946,561,-683,654,-947,349,116,797,421,572,197,733,-353,910,721,18,249,-193,549,887,391,204,-115,157,65,881,190,617,199,101,995,849,51,-753,25,766,812,571,-849,39,881,674,969,413,-57,905,-236,121,688,901,284,697,-40,691,805,-221,-199,633,746,116,449,665,733,-299,141,281,749,112,152,6,355,169,-615,121,288,689,497,561,-271,-717,589,496,-581,337,69,861,318,-694,533,849,181,991,-841,216,546,96,-416,161,-897,961,110,-887,34,896,95,-370,-21,-753,-636,133,-35,-865,-585,-497,-464,501,291,137,319,99,-761,556,163,-901,41,13,286,353,-300,456,834,857,251,-645,-839,-227,534,946,947,625,-376,-649,705,-771,-566,68,-769,-501,25,-637,743,821,846,87,384,-638,691,121,105,302,509,585,781,651,349,-353,901,-881,401,-873,-969,689,-870,443,-41,707,-752,-309,6,821,-714,-51,766,821,849,-1,-216,-639,-541,-385,481,286,-726,681,841,326];